package algorithm.sort;

/**
 * 希尔排序:分组,然后逐渐增加每组中元素的个数
 * 希尔排序就是简单插入排序的一般化,只是变更了gap的值,其对比逻辑和插入排序是相同的
 * @author jiaqi.han
 * @date 2021年3月24日
 */
public class ShellSort extends CommonSort implements Sortable {

	public void sort(int[] targetArr) {
		int temp;
		int preIndex;
		int gap = targetArr.length / 2;
		while (gap > 0) {
			for (int i = gap; i < targetArr.length; i++) {
				temp = targetArr[i];
				preIndex = i - gap;
				while (preIndex >= 0 && temp < targetArr[preIndex]) {
					targetArr[preIndex + gap] = targetArr[preIndex];
					preIndex -= gap;
				}
				targetArr[preIndex + gap] = temp;
			}
			gap /= 2;
		}
		displaySortedArray(-1, targetArr);
	}
}
